﻿//排序
//思路先写单趟，再整体
#include"排序.h"
//实现数组的有序：end的起始位置在0：从只有一个数开始
//    将数组的前1个数当作一个有序数组，把第2个数插入
//    将数组的前2个数当作一个有序数组，把第3个数插入......
//这样就能实现数组的有序
//               end的结束位置在数组的第n-1个



void PrintA(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

//单个数据插入的有序方式
//
// 时间复杂度：O(N)
//
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)//套到一层控制end的起始位置的循环即可
	{
		//思路，从后往前依次比较，如果比x大就放到x位置的后面，比x小就放到x的前面，放到-1位置的时候停止
		//移动数据的时候小心覆盖原数据的问题，要先保存
		int end = i;
		int tem = a[end + 1];//保存这个要插入的数据，即最后一位后面的数据
		while (end >= 0)//放到-1位置的时候停止
		{
			//第一种情况：放入的数小于end：将end位置得数向后移动，原end位空出待插入

			if (tem < a[end])
			{
				a[end + 1] = a[end];
				--end;//放完数据，end一定记得往前移
			}
			else
				//第二种情况：放入的数不小于end：直接赋值给end+1位置
			{
				//a[end + 1] = tem;   |
				break;           //   |
			}                    //   |
								 //   V
		}
		//也可以在循环外面写21行的步骤，直接解决上面循环的另一种可能：比所有值都小：放在了第-1个位置的问题
		a[end + 1] = tem;//两种出口合一解决方式
	}
}

//交换的函数
void Swap(int* p1, int* p2)
{
	//中间值交换法
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

////
// 时间复杂度：O(N^2)
//最好的情况下:O(N)

void BubbleSort(int* a, int n)
{
	//结束位置（边界很重要）！！！
	//第一个for循环的j增大;控制单次冒泡的结束位置：逐渐缩小
	for (int j = 0; j < n-1; j++)//单次变整体：控制冒泡排序的结束位置：到最后一位的前一个
	{
		//优化：如果一个数组本来就有序，则为节省时间：加入exchange
		int exchange = 0;//-----------------------------------------------------

		//一趟冒泡
		for (int i = 1; i < n-j; i++)//从结束位置最后，往前面排：n-j（）
		//每一次只能排出一个最大数放在后面
		{
			if (a[i - 1] > a[i]) //不满足顺序就交换
			{
				Swap(&a[i - 1], &a[i]);
				//如果发函恶搞了交换
			}
		}
		//如果exchange的值没有被修改：没有发生交换：直接跳出循环，进行下一单趟
		if (exchange == 0)//---------------------------------------------------
		    break;
	}
}

//希尔排序：
// **优点：预排序过程中一次性可以挪动的单位变多，更快的移动到更有序的位置
// **比原插入排序更快
//两个部分:1，预排序--目标：接近有序
//        2，插入排序--目标:有序

//分组插入排序：目标：大的数更快的换到后面的位置：小的数更快跳到前面的位置
//间距：间距为a的（a个数）分为一组：对每一组进行插入排序：end的位置从前往后。将后面的两个数据分两次（a-1）插入排序......
//{1，2，3，4，5，6，7，8，9}
// |  |  |  |  |  |  |  |  |
// ------------------
//    |  |     |  |     |  |
//    -------------------
//       |        |        |
//       -------------------
//       {----a---}//间距为a的三个数进行从0-a的插入排序


void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		//除到最后的一趟：gap为1：插入排序
		gap = gap / 3 + 1;


		//所有的间距为gap的组排序;再套一层循环:实现起始位置的挪动，每次往后移动一个单位
		//for (int j = 0; j < gap; j++)//间距为gap就需要0到gap-1次分组排序
		
			//间距为gap的1组排序：


			//优化：直接只用一层循环：将i += gap变为i++因为所有的分组放在一起看其实都是间隔为1的长度为gap的小组
			for (int i = 0; i < n - gap; i++)//这里需要把133行的代码删掉
			//for (int i = 0; i < n - gap; i += gap)//完成多次间距为gap的交换，只需控制end位置
			{                        // --------------------------------------|                                         
				//定义：间距，尾位置，保存的插入数据                             |
				//                                                            |
				int end = i;         //-----------------------------------------
				int tem = a[end + gap];
				//tem值小于end则交换：把end的值赋值给tem==end+gap位置(覆盖)

				//实现正确顺序的交换
				while (end >= 0)
				{
					if (tem < a[end])
					{
						a[end + gap] = a[end];//向后覆盖：只要tem没找到比自己小的数就一直向后覆盖，直到第0个位置都没找到，覆盖后，下一行代码执行end-gap<0跳出循环，将tem插入到第0个位置
						end -= gap;//end小于0跳出
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tem;//向前覆盖：放入待插入的值tem

				//133/141组合完成完整交换
			}
			//5 3 2为例：3 5进入一次while，交换为3 5 2
			//           for改动end值 == gap
			// while：gap向后覆盖(gap+gap)但没有break：覆盖为3 5 5，
			// 且end=0满足while条件，继续while:此时的2<3满足条件：3（0位置）向5（0+gap）位置覆盖：覆盖为：3 3 5,
			//最后end=0-gap:跳出while，将tem=2覆盖到0的位置：得到结果：2 3 5


			PrintA(a,n);
			//每一组排完都打印一下：观察慢慢变有序的过程
		}
		//***每一循环的目的和结束位置很关键，数据的覆盖和tem插入的时机也很关键***


}


//gap值的问题:1,gap越大，数据跳的越快，但越不接近有序，可能跳到离谱的位置
//           2,gap越小，数据跳的越慢，但越接近有序：gap=1时就是插入排序



//选择排序；最大最小放两边;向内收缩
void SelectSort(int* a, int n)
{
	//定义两个值:表示下标值，一个最左边，另一个最右边
	int begin = 0, end = n - 1;

	//选出最小/最大值的位置(下标值)
	//用min/max代表其中最小/大的数下标

	while (begin < end)
	{

		int min = begin, max = begin;//最大最小的值起始都是第一个位置的下标
		//然后让剩下的值和他们比较
		for (size_t i = begin + 1; i <= end; i++)//从前往后找
		{
			if (a[i] < a[min]) //小的数
			{
				min = i;//下标的值赋给min
			}
			if (a[i] > a[max])//大的数
			{
				max = i;//下标的值赋给max
			}
		}
		//找到下标值：交换数据
		//最小值换到左边，最大值换到右边
		Swap(&a[begin], &a[min]);
		//特殊情况:当只剩下三个数据选择时，将最小的换到前面已经完成，
		//但是最大的同时也到了最后面-->得到了正确顺序，后续的end和原max的位置交换，又会把顺序颠倒得到相反的顺序❌
		//*第一步的交换是没问题的;要限制第二次的交换
		//解决方法：增加一个判断语句：判断max本来是否在最前面，需要换为最小值
		if (max == begin)
		{//如果是：则将min的下标值赋给max                                      
			max = min;
		}
		Swap(&a[end], &a[max]);//206后，end就会与原来位置的数据进行交换==不变
		//向内收缩比较
		begin++;
		end--;

		PrintA(a, n);
	}
}



//快速排序
// 
// 
//二叉树结构的交换排序方法原理：
//任取待排序元素序列中的某元素作为基准值，
// 按照该排序码将待排序集合分割成两子序列，
// 左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，
// 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
//     左子小于右子

//排序方法：
//选定一个key，两个移动的指针，
// key在左边，让右边先走（先找）
// 左边找比key小的数值，右边找比key大的数值，左右做交换，
// 找到了就不再移动，找到就继续移动，直到相遇
// 相遇的时候如果此值小于key则与key位置的值交换，否则不交换
//目的;key的值放到了最终位置，左比它小，右比他大

//排序结果：
//此时如果左边的数和右边的数（树）也用同样的方法将正确的值放好，那么最终所有的数都能到正确的位置：实现了排序
//特殊情况:最后区间只剩一个值，或者没有值了....
//



// 
//快排排序：

void QuickSort(int* a, int left, int right)
{
	//当区间只有一个值或者不存在时;就是最小子问题：不再进行程序
	if (left >= right)
		return;

	//为了避免最坏的情况，每次都取到最小的数为key
	//创立一个随机值，随机来选择key值
	//int randi = rand() % (right - left + 1);
	// 对这个区间取模：保证取到的随机值在left到right之间
	//randi += left;//得到的值还要在起始下标left上面加，left会因为递归分组变化
	//Swap(&a[left], &a[randi]);//交换这两个下标对应的值（把基准值换到最左边），因为快排的逻辑还是最左边为key（基准值）

	//小区间优化：插入排序：减少90%左右的递归
	//if (right - left + 1 < 15)//区间内的个数已经小于15了，就可以用插入排序了
	//{
	//	InsertSort(a + left, right - left + 1);
		//         从左开始      个数=差+1
		//进行插入排序时：开始的位置只需要从中间和后面的开始插入，因为前面
	//}





	//尽量最好的情况：方案：三数取中
	//int mid = GetMid(a, left, right);
	//Swap(&a[left], &a[right]);


	int begin = left  , end = right  ;//递归时候传参：因为left，right的值已经改变，不能每次都用初始化的值

	int key = left;//key在左就让最右边的指针先移动
	//3         6         1
	//key
	//left              right
	//
	while (left < right)//出循环==相遇
	{
		//指针移动，做交换
		// 
		//right先走，找小
		while (left < right && a[right] >= a[key])//找到相等的值就继续走，因为在左边右边都可以
		{
			--right;//没找到小的，继续找，左移动

		}
		//找到了，停止：跳出让left走


		//left再走，找大
		while (left < right && a[left] <= a[key])
		{
			++left;//没找到大的，继续找，右移动
		}
		//找到了...
		
		//做交换...
		Swap(&a[left], &a[right]);
	}
	//当相遇时，出循环，让key和left做交换
	Swap(&a[left], &a[key]);

	key = left;//数据交换后，下标也要做交换：把left放回到最左边，key到达正确位置

	//这里做完后，得到的是一个正确的位置，和两边的两个需要排序的数组
	//***递归的思路：
	//左边的区间：begin->key-1,右边的区间：key+1->right
	//左右两个区间分别继续走上面的单趟排序......
	QuickSort(a, begin, key - 1);
	QuickSort(a, key+1, end);
	
}

//快速排序的时间复杂度：O(N*logN)
//最坏情况：O(N^2):每次选到的key都是最小值，最偏的位置，要分无数个两边
//解决方案：用随机数决定key

//最好情况：每次都选到中位数：
//接解决方案：三数取中：left mid right
//取不是最大也不是最小的那个值
/*
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid < a[right]])
		{
			return mid;
		}
		//走到下一步则：mid最大，下面判断剩下的谁大，谁大谁居中
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid > a[right]])
		{
			return mid;
		}
		//走到下一步则：mid最大，下面判断剩下的谁大，谁大谁居中
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//优化：小区间优化
//二叉树的递归，最后的几层占了整个排序的大部分
//我们可以通过在最后几层用其他排序方式：最好用插入排序，来减少递归
*/